package org.aplombh.java.awcing.basic.basics.search.binarySearch;

import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
 * <p>
 * 对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
 * <p>
 * 如果数组中不存在该元素，则返回 -1 -1。
 * <p>
 * 输入格式
 * 第一行包含整数 n 和 q，表示数组长度和询问个数。
 * <p>
 * 第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
 * <p>
 * 接下来 q 行，每行包含一个整数 k，表示一个询问元素。
 * <p>
 * 输出格式
 * 共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
 * <p>
 * 如果数组中不存在该元素，则返回 -1 -1。
 * <p>
 * 数据范围
 * 1≤n≤100000
 * 1≤q≤10000
 * 1≤k≤10000
 * 输入样例：
 * 6 3
 * 1 2 2 3 3 4
 * 3
 * 4
 * 5
 * 输出样例：
 * 3 4
 * 5 5
 * -1 -1
 */
public class ScopeOfNumber_789 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] ints = new int[n];

        IntStream.range(0, n).forEach(i -> ints[i] = scanner.nextInt());
        IntStream.range(0, m).forEach((i) -> {
            int x = scanner.nextInt();
            int left, right;

            // find left margin of the number
            // 如果 x <= j 则满足条件的数在左边,找到数组最左边满足条件的数
            left = MyBinarySearch.binarySearchLeftMargin(ints, j -> x <= j, 0, n - 1);

            // find right margin of the number
            if (ints[left] != x)
                System.out.println("-1 -1");
            else {
                System.out.print(left + " ");

                // 如果 x >= j 则满足条件的数在右边，找到数组最右边满足条件的数
                right = MyBinarySearch.binarySearchRightMargin(ints, j -> x >= j, 0, n - 1);
                System.out.println(right);
            }
        });
    }
}